[LCT][线段树]树点涂色

树点涂色

Time Limit: 10 Sec Memory Limit: 128 MB

Description

Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：

1 x:

把点x到根节点的路径上所有的点染上一种没有用过的新颜色。

2 x y:

求x到y的路径的权值。

3 x:

在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行m次操作

Input

第一行两个数n,m。

接下来n-1行，每行两个数a,b，表示a与b之间有一条边。

接下来m行，表示操作，格式见题目描述。

Output

每当出现2,3操作，输出一行。

如果是2操作，输出一个数表示路径的权值

如果是3操作，输出一个数表示权值的最大值

Sample Input

5 6
　1 2
　2 3
　3 4
　3 5
　2 4 5
　3 3
　1 4
　2 4 5
　1 5
　2 4 5

Sample Output

3
　4
　2
　2

HINT

1<=n,m<=100000

Solution

我们将边两端的点颜色相同的边设为实边，不同的设为虚边。那么一次新增颜色的操作显然就是LCT的access操作！access的时候恰是虚边和实边的转换。

那么我们只要用线段树维护每个点到根的贡献，结合dfs序来实现子树加，每次在LCT进行access的时候进行±1修改，然后询问的时候用区间求和，区间最值求得答案即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 2e5+5;

int n,m;
int x,y,P;
int POS[ONE],POSCNT;
int pos[ONE],dfn_cnt,size[ONE],dfn[ONE];
int Dep[ONE],son[ONE],Top[ONE];
int lc[ONE],rc[ONE],fa[ONE],fat[ONE];
int res_max,res_value;

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

namespace tree
{
    int next[ONE],first[ONE],go[ONE],tot=0;

    void Add(int u,int v)
    {
        next[++tot]=first[u];    first[u]=tot;    go[tot]=v;
        next[++tot]=first[v];    first[v]=tot;    go[tot]=u;
    }

    void Dfs(int u,int father)
    {
        pos[u] = ++dfn_cnt; dfn[dfn_cnt] = u;
        size[u] = 1;
        Dep[u] = Dep[father] + 1;
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father) continue;
            fa[v] = u;    fat[v] = u;
            Dfs(v,u);
            size[u] += size[v];
            if(size[v] > size[son[u]]) son[u] = v;
        }
    }

    void Dfs_twice(int u,int father)
    {
        POS[u] = ++POSCNT;
        if(son[u])
        {
            int v=son[u];
            Top[v] = Top[u];
            Dfs_twice(v,u);
        }

        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father || v==son[u]) continue;
            Top[v] = v;
            Dfs_twice(v,u);
        }
    }

    int LCA(int x,int y)
    {
        while(Top[x]!=Top[y])
        {
            if( Dep[Top[x]] < Dep[Top[y]] ) swap(x,y);
            x = fat[Top[x]];
        }
        if(POS[x] > POS[y]) swap(x,y);
        return x;
    }
}

namespace Seg
{
    struct power
    {
        int add,value;
        int maxx;
    }Node[ONE*4];

    void pushdown(int i,int Q)
    {
        if(Node[i].add)
        {
            Node[i<<1].add += Node[i].add;
            Node[i<<1|1].add += Node[i].add;
            Node[i<<1].maxx += Node[i].add;
            Node[i<<1|1].maxx += Node[i].add;
            Node[i<<1].value += Node[i].add * (Q-Q/2);
            Node[i<<1|1].value += Node[i].add * (Q/2);
            Node[i].add = 0;
        }
    }

    void Build(int i,int l,int r)
    {
        if(l==r)
        {
            Node[i].value = Dep[dfn[l]];
            Node[i].maxx = Dep[dfn[l]];
            return ;
        }
        int mid = l+r>>1;
        Build(i<<1,l,mid);    Build(i<<1|1,mid+1,r);
        Node[i].value = Node[i<<1].value + Node[i<<1|1].value;
        Node[i].maxx = max(Node[i<<1].maxx, Node[i<<1|1].maxx);
    }

    void Update(int i,int l,int r,int L,int R,int x)
    {
        if(L<=l && r<=R)
        {
            Node[i].add += x;
            Node[i].value += (r-l+1)*x;
            Node[i].maxx += x;
            return;
        }
        pushdown(i,r-l+1);
        int mid = l+r>>1;
        if(L<=mid) Update(i<<1,l,mid,L,R,x);
        if(mid+1<=R) Update(i<<1|1,mid+1,r,L,R,x);

        Node[i].value = Node[i<<1].value + Node[i<<1|1].value;
        Node[i].maxx = max(Node[i<<1].maxx , Node[i<<1|1].maxx);
    }

    void Query(int i,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)
        {
            res_max = max(res_max,Node[i].maxx);
            res_value += Node[i].value;
            return;
        }
        pushdown(i,r-l+1);
        int mid = l+r>>1;
        if(L<=mid) Query(i<<1,l,mid,L,R);
        if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);
    }
}

namespace LCT
{
    int is_real(int x)
    {
        return (lc[fa[x]]==x || rc[fa[x]]==x);
    }

    void Turn(int x)
    {
        int y = fa[x], z = fa[y];
        int b = x==lc[y] ? rc[x]:lc[x];

        fa[x] = z;    fa[y] = x;
        if(b) fa[b] = y;

        if(z)
        {
            if(y == lc[z]) lc[z] = x;
            else
                if(y == rc[z]) rc[z] = x;
        }

        if(x==lc[y]) rc[x]=y,lc[y]=b;
        else lc[x]=y,rc[y]=b;
    }

    void Splay(int x)
    {
        while(is_real(x))
        {
            if(is_real(fa[x]))
            {
                if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x])) Turn(fa[x]);
                else Turn(x);
            }
            Turn(x);
        }
    }

    int find_root(int x)
    {
        while(lc[x]) x=lc[x];
        return x;
    }

    void access(int x)
    {
        for(int p=x,q=0; p; q=p,p=fa[p])
        {
            Splay(p);
            if(rc[p])
            {
                int N = find_root(rc[p]);
                Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,1);
            }

            rc[p] = q;
            if(rc[p])
            {
                int N = find_root(rc[p]);
                Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,-1);
            }
        }
    }
}

int Getsum(int x,int y)
{
    int Ans, Sx, Sy, SLCA, LCA;
    LCA = tree::LCA(x,y);
    x=pos[x],    y=pos[y],    LCA=pos[LCA];
    res_value = 0;    Seg::Query(1,1,n,x,x);    Sx = res_value;
    res_value = 0;    Seg::Query(1,1,n,y,y);    Sy = res_value;
    res_value = 0;    Seg::Query(1,1,n,LCA,LCA);    SLCA = res_value;
    return Sx+Sy-2*SLCA+1;
}

int Getmax(int x)
{
    res_max = 0;
    Seg::Query(1,1,n,pos[x],pos[x]+size[x]-1);
    return res_max;
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n-1;i++)
    {
        x=get();    y=get();
        tree::Add(x,y);
    }

    tree::Dfs(1,0);
    Top[1] = 1, tree::Dfs_twice(1,0);
    Seg::Build(1,1,n);

    while(m--)
    {
        P = get();    x=get();
        if(P==1)
            LCT::access(x);
        if(P==2)
            y=get(), printf("%d\n",Getsum(x,y));
        if(P==3)
            printf("%d\n",Getmax(x));
    }
}